package real.byteDance;

public class Ant {
    //一个蚂蚁在时钟上从12点出发，每次可以顺时针或逆时针走一个刻度
    // ，总共走n步，问最终刚好回到12点的走法有多少种
    public int antStep(int n){
        if(n % 2 != 0){
            return  -1;
        }

        long result = 1;
        for (int i = 0; i < n/2; i++) {
            result = result * (n - i) / (i + 1);
        }
        return (int) result;
    }


    public int antStep1(int n){
        // 如果n是奇数，无法回到原点
        if(n % 2 != 0){
            return -1;
        }

        // 方法1: 使用动态规划
        // dp[i][j] 表示走i步后，相对于起点顺时针偏移j步的方案数
        // 由于时钟是环形的，偏移量范围是[-n, n]，为方便处理，加上偏移量n映射到[0, 2n]
        int[][] dp = new int[n+1][2*n+1];
        int offset = n; // 偏移量

        // 初始状态：走0步在起点
        dp[0][offset] = 1;

        // 状态转移
        for(int i = 1; i <= n; i++){
            for(int j = 0; j <= 2*n; j++){
                // 从左边位置顺时针走一步
                if(j > 0){
                    dp[i][j] += dp[i-1][j-1];
                }
                // 从右边位置逆时针走一步
                if(j < 2*n){
                    dp[i][j] += dp[i-1][j+1];
                }
            }
        }

        // 返回走n步后回到起点的方案数
        return dp[n][offset];
    }
}
